# Kruskal：搜索图中最小边，连接子树

from tools.Input import Input
from tools.Output import Output
from tools.Tree import Tree


class Kruskal:
    __name = 'Kruskal'

    @staticmethod
    def do_mst():
        # g = Input.input_graph()  # 输入无向图
        g = Input.get_graph1()  # 获取一个图（例3.2.1）
        print('输入的图为：')
        Output.print_graph_set(g)

        s_set = g[1]  # 图的边集
        trees = []  # 形成的森林，存放生成树的列表
        ts_len = 0  # 加入边的数量

        print('生成过程：')
        while True:
            if len(s_set) == 0:  # 边集大小为0
                print('输入的图不连通')
                return

            s_name_min = min(s_set, key=lambda k: s_set[k])  # 边集中找到权重最小的边

            if len(trees) == 0:  # 没有树
                new_tree, sign = Tree.add_node(None, {s_name_min: s_set[s_name_min]})  # 生成一棵树
                trees.append(new_tree)  # 加入到树集合中
                print('生成一颗树', new_tree)
            else:  # 树列表不为空
                v1 = s_name_min[0]  # 顶点1
                v2 = s_name_min[1]  # 顶点2

                v1_in_tree = None  # v1所在的树
                v2_in_tree = None  # v2所在的树
                for tree in trees:
                    if Tree.in_tree(tree=tree, v=v1):
                        v1_in_tree = tree
                    if Tree.in_tree(tree=tree, v=v2):
                        v2_in_tree = tree

                if v1_in_tree == v2_in_tree:  # v1和v2所在的树相同
                    if v1_in_tree is None and v2_in_tree is None:  # 都为空
                        new_tree, sign = Tree.add_node(None, {s_name_min: s_set[s_name_min]})  # 生成一棵树
                        trees.append(new_tree)  # 加入到树集合中
                        print('生成一棵树', new_tree)
                    else:  # 在一颗树中，加入边会形成环
                        print('加入', v1, v2, '会形成环，跳过')
                        s_set.pop(s_name_min)  # 直接跳过
                        continue
                elif v1_in_tree is not None and v2_in_tree is not None:  # v1、v2分别在不同的树中
                    new_tree, sign = Tree.forest_tree(v1_in_tree, v2_in_tree, {s_name_min: s_set[s_name_min]})  # 合并为一棵树
                    trees.remove(v1_in_tree)
                    trees.remove(v2_in_tree)
                    trees.append(new_tree)
                    print('树', v1_in_tree, '\n树', v2_in_tree, '\n合并为新树', new_tree)
                elif v1_in_tree is not None:  # v1在树中，v2不在树中
                    new_tree, sign = Tree.add_node(v1_in_tree, {s_name_min: s_set[s_name_min]})  # 将边加入v1所在树中
                    trees.remove(v1_in_tree)
                    trees.append(new_tree)  # 更新树列表
                    print('树', v1_in_tree, '新增节点', {s_name_min: s_set[s_name_min]})
                elif v2_in_tree is not None:  # v2在树中，v1不在树中
                    new_tree, sign = Tree.add_node(v2_in_tree, {s_name_min: s_set[s_name_min]})  # 将边加入v2所在树中
                    trees.remove(v2_in_tree)
                    trees.append(new_tree)  # 更新树列表
                    print('树', v2_in_tree, '新增节点', {s_name_min: s_set[s_name_min]})

            s_set.pop(s_name_min)  # 从边集中取出边
            ts_len = ts_len + 1  # 加入边的数量+1
            if ts_len == len(g[0]) - 1:  # 边数=顶点数-1时停止
                break

        tree = trees[0]
        print('最小生成树为：')
        Output.print_graph_set(tree)
